package com.gxc.array;

import com.gxc.print.BooleanPrint;

/**
 * 3152. 特殊数组 II

 * 如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。
 *
 * 周洋哥有一个整数数组 nums 和一个二维整数矩阵 queries，对于 queries[i] = [fromi, toi]，
 * 请你帮助周洋哥检查子数组 nums[fromi..toi] 是不是一个 特殊数组 。
 *
 * 返回布尔数组 answer，如果 nums[fromi..toi] 是特殊数组，则 answer[i] 为 true ，否则，
 * answer[i] 为 false 。
 */
public class IsArraySpecial2 {

    public static void main(String[] args) {
       /* BooleanPrint.print(handle2(new int[]{3,4,1,2,6}, new int[][]{
                {0,4}
        }));
        BooleanPrint.print(handle2(new int[]{4,3,1,6}, new int[][]{
                {0,2}, {2,3}
        }));*/

        BooleanPrint.print(dp(new int[]{7,3,3,9}, new int[][]{
                {1,2},{0,3},{1,2},{0,1},{1,2},{0,3},{2,2},{0,1}
        }));
    }

    /**
     * 遍历循环
     * @param nums
     * @param queries
     * @return
     */
    public static boolean[] handle(int[] nums, int[][] queries) {
        boolean[] res = new boolean[queries.length];

        for (int i = 0; i < queries.length; i++) {
            int start = queries[i][0];
            int end = queries[i][1];

            for (int j = start+1; j <= end; j++) {
                if (nums[j-1] %2 == nums[j]%2) {
                    res[i] = false;
                    break;
                }
            }
            res[i] = true;
        }

        return res;
    }

    public static boolean[] handle2(int[] nums, int[][] queries) {
        boolean[] res = new boolean[queries.length];

        for (int i = 0; i < queries.length; i++) {
            int start = queries[i][0];
            int end = queries[i][1];

            //用已有结果快速计算  res[i] = false      queries[j][0]<queries[i][0]    queries[j][1]>queries[i][1]     res[j] = false
            //  res[i] = true   queries[j][0]>queries[i][0]    queries[j][1]<queries[i][1]     res[j]=true
            boolean isbreak = false;
            for (int j = 0; j < i; j++) {
                if (!res[j] && start<queries[j][0] && end>queries[j][1]) {
                    res[i] = false;
                    isbreak = true;
                    break;
                } else if (res[j] && start>queries[j][0] && end<queries[j][1]) {
                    res[i] = true;
                    isbreak = true;
                    break;
                }
            }

            if (isbreak) continue;
            res[i] = true;
            for (int j = start+1; j <= end; j++) {
                if (nums[j-1] %2 == nums[j]%2) {
                    res[i] = false;
                    break;
                }
            }
        }

        return res;
    }

    public static boolean[] dp(int[] nums, int[][] queries) {
        //以i结尾，最长有多少位的特殊数组
        int[] dp = new int[nums.length];
        dp[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            //奇偶性不同
            if (((nums[i-1] + nums[i]) & 1) == 1) {
                dp[i] = dp[i-1]+1;
            } else {
                dp[i] = 1;
            }
        }

        boolean[] res = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int start = queries[i][0];
            int end = queries[i][1];

            if (end - start + 1 <= dp[end]) {
                res[i] = true;
            } else {
                res[i] = false;
            }
        }
        return res;
    }
}
